package com.yanyuan.algorithm.sort;

/**
 * @Description 插入排序
 * 每次从未排序列表中，拿出第一个值放到已排序列表中
 * （部分数据已排序的情况，效率高于冒泡/选择）
 * @Author yanyuan
 * @Date 21:21 2020/4/25
 * @Version 1.0
 **/
public class InsertionSort {

    public static int arr[] = new int[]{60, 50, 30, 10, 20};

    public static int n = arr.length;

    public static int[] sort(){
        for(int i = 1; i < n; i++){
            int temp = arr[i];//存放临时数据
            int j = i - 1; //存放已经排序的元素
            //内层循环插入排序
            while(j >= 0 && arr[j] > temp){
                arr[j+1] = arr[j];
                j--;

            }
            arr[j+1] = temp;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] sortArr = InsertionSort.sort();
        for (int val : sortArr){
            System.out.print(" " + val);
        }
    }
}
